#!/usr/bin/env python

"""
- Remember to change the above line to fit your environment
- Python >= 2.5 is required
- Read the LICENSE file before redistributing/modifying this software
"""

import sigma
import covering

class FSM:
    """
    A simple Finite State Machine (de)serializer

    Example:
    spec = 'i:q0,q1,f:q2,f:q3#q0-a-q1,q0-b-q1,q1-c-q0,q1-d-q3'
     - the part before the # defines the state set along with initial/final states (prefixed by i:/f: respectively)
     - the initial state is unique
     - the part after the # defines the transitions in the simple 'from_state-input-to_state' notation
    """
    states = []
    initial = None
    finals = []
    transitions = {}
    possible_inputs = {}
    spec = None
    sigma = []

    def __init__(self, spec = None, back_size = None, sigma = None):
        import random
        if spec is not None:
            self.spec = spec
            for state in spec.split('#')[0].split(','):
                if state[0:2] == 'i:':
                    self.initial = state[2:]
                    self.states.append(self.initial)
                elif state[0:2] == 'f:':
                    self.finals.append(state[2:])
                    self.states.append(state[2:])
                else:
                    self.states.append(state)

            for tran in spec.split('#')[1].split(','):
                start = tran.split('-')[0]
                input = tran.split('-')[1]
                end = tran.split('-')[2]
                if start in self.states:
                    self.transitions[start + ',' + input] = end
                    if start not in self.possible_inputs.keys():
                        self.possible_inputs[start] = [input]
                    else:
                        self.possible_inputs[start].append(input)
        elif len(sigma) > 0:
            if back_size is None:
                import random
                random.seed()
                back_size = random.randint(0, int(len(sigma)/2))
            self.random_local(back_size, sigma)
            self.spec = ''
            for st in self.states:
                if st in self.initial:
                    self.spec += 'i:' + st
                elif st in self.finals:
                    self.spec += 'f:' + st
                else:
                    self.spec += st
                self.spec += ','
            self.spec = self.spec[:-1]
            self.spec += '#'
            for da,a in self.transitions.iteritems():
                self.spec += da.replace(',', '-') + '-' + a
                self.spec += ','
            self.spec = self.spec[:-1]
            

    def __repr__(self):
        return str(self.spec)

    def __len__(self):
        return len(self.states)

    def get_transition(self, state, input):
        return self.transitions[state + ',' + input]

    def can_read(self, input, state):
        try:
            return input in self.possible_inputs[state]
        except KeyError:
            return False

    def random_local(self, back_size, sigma, self_loops = False):
        import random
        edges = 0
        alpha = ['']
        self.sigma = [str(x) for x in sigma.symbols]
        alpha.extend(self.sigma)
        self.states = ['q0']
        self.transitions = {}
        self.possible_inputs = {}
        self.initial = 'q0'
        self.finals = ['q' + str(len(alpha) - 1)]
        self.possible_inputs['q0'] = [alpha[1]]
        
        if back_size > 0:
            max_back_size = int(((len(alpha) - 1) * len(alpha)) * 0.5)
            if self_loops:
                max_back_size += len(alpha) - 1
            if back_size > max_back_size:
                back_size = max_back_size

        for i in range(1, len(alpha)):
            self.states.append('q' + str(i))
            self.transitions['q' + str(i - 1) + ',' + alpha[i]] = 'q' + str(i)

            if 'q' + str(i) in self.possible_inputs.keys():
                self.possible_inputs['q' + str(i - 1)].append(alpha[i])
            else:
                self.possible_inputs['q' + str(i - 1)] = [alpha[i]]

        couples = []
        while back_size > 0:
            random.seed()
            couple = tuple([random.choice(range(1, len(alpha))), random.choice(range(1, len(alpha)))])
            if couple[0] > couple[1]:
                couple = tuple([couple[1], couple[0]])
            if couple not in couples:
                couples.append(couple)
                back_size -= 1
                self.transitions['q' + str(couple[1]) + ',' + alpha[couple[0]]] = 'q' + str(couple[0])
                
                if 'q' + str(couple[1]) in self.possible_inputs.keys():
                    self.possible_inputs['q' + str(couple[1])].append(alpha[couple[0]])
                else:
                    self.possible_inputs['q' + str(couple[1])] = [alpha[couple[0]]]

    def dotit(self, program = 'dot', file = 'automaton.png', caption = None, debug = False):
        dotcode = 'digraph Automaton {\n'
        dotcode += 'rankdir=LR;\n'
        dotcode += 'graph[fontname = "Palatino",fontsize=10'
        if caption:
            dotcode += 'label="'+caption+'"];\n';
        else:
            dotcode += '];\n'
        dotcode += 'node[fontname = "Palatino",margin=0.0,shape=doublecircle,fontsize=10,style="setlinewidth(0.5)"];' + ' '.join(self.finals) + ';\n';
        dotcode += 'node[fontname = "Palatino",margin=0.0,shape=circle,fontsize=10,style="setlinewidth(1.5)"];' + self.initial + ';\n';
        dotcode += 'node[fontname = "Palatino",margin=0.0,shape=circle,fontsize=10,style="setlinewidth(0.5)"];\n'
        for start,end in self.transitions.iteritems():
            dotcode += '\t' + start.split(',')[0] + ' -> ' + end + '[arrowtype="open",arrowsize=0.5,style="setlinewidth(0.5)", label = "' + start.split(',')[1] + '",fontsize=10,fontname="Palatino" ];\n'
        dotcode += '}'

        if debug:
            print dotcode

        if file is not None:
            import pydot
            pydot.graph_from_dot_data(dotcode).write_png(file, prog = program)
        return dotcode

    def test_string(self, string):
        state = self.initial
        cursor = 0
        while cursor < len(string):
            symbol = string[cursor]
            if symbol in self.possible_inputs[state]:
                state = self.transitions[state + ',' + symbol]
                cursor += 1
            else:
                return False

        return True

    def random_string(self, min = 10, max = 1000, length = None):
        import random
        string = self.accepted_string(min, max, length)
        random.shuffle(string)
        return string

    def random_trace(self, covering, min = 10, max = 1000, length = None, swappings = None, debug = False):
        import random
        if length is None:
            length = random.randint(min, max)

        string = self.accepted_string(min, max, length)
        length = len(string)
        original = ','.join(str(x) for x in string)

        if swappings is None:
            swappings = random.randint(int(length/4), int(length/2))
        elif swappings >= length:
            swappings = length - 1

        n = 0
        if debug:
            print 'SWAPPINGS:', swappings
            print 'COVERING:', covering

        while n < swappings:
            random.seed()
            idx = random.randint(0, length - 1)
            if idx == length - 1:
                left = string[idx - 1]
                right = string[idx]
                if set(covering.cliques_of(left)) & set(covering.cliques_of(right)) == set([]):
                    string[idx - 1] = right
                    string[idx] = left
            else:
                left = string[idx]
                right = string[idx + 1]
                if set(covering.cliques_of(left)) & set(covering.cliques_of(right)) == set([]):
                    string[idx] = right
                    string[idx + 1] = left
            n += 1
        
        return (original, string)
        

    def accepted_string(self, min = 10, max = 1000, length = None):
        import random
        string,letter = [],''
        state = self.initial

        if length is None:
            length = random.randint(min, max)

        while state not in self.finals:
            random.seed()
            letter = random.choice(self.possible_inputs[state])
            state = self.transitions[state + ',' + letter]
            string.append(letter)

        return string

    def mutated_accepted_string(self, min = 10, max = 1000, length = None, mutations = None, debug = False):
        import random
        if length is None:
            length = random.randint(min, max)

        string = self.accepted_string(min, max, length)
        length = len(string)
        if debug:
            print ','.join(str(x) for x in string)

        if mutations is None:
            mutations = random.randint(int(length/4), int(length/2))
        elif mutations >= length:
            mutations = length - 1

        n = 0
        if debug:
            print 'MUTATIONS:', mutations

        while n < mutations:
            random.seed()
            idx = random.randint(0, length - 1)
            if idx == length - 1:
                left = string[idx - 1]
                right = string[idx]
                string[idx - 1] = right
                string[idx] = left
            else:
                left = string[idx]
                right = string[idx + 1]
                string[idx] = right
                string[idx + 1] = left
            n += 1
        
        return string

def main():
    # Remember that a local automaton has len(S) + states
    sig = sigma.Sigma(size = 5)
    f = FSM(sigma = sig, back_size = 0)

    """
    # Uncomment region to test against accepted strings
    print 'TESTING ACCEPTED STRING:'
    accepted_string = f.accepted_string()
    #print accepted_string
    print f.test_string(accepted_string)
    """

    """
    # Uncomment region to create a PNG of the automaton
    capt = 'Accepted string: ' + str(accepted_string) + ', Sigma: ' + ', '.join(str(x) for x in f.sigma) + ', |Q| = ' + str(len(f))
    f.dotit(caption = capt)
    """
    
    """
    print 'TESTING MUTATED ACCEPTED STRING:'
    mutated_accepted_string = f.mutated_accepted_string()
    #print mutated_accepted_string
    print f.test_string(mutated_accepted_string)
    """

    print 'TESTING RANDOM TRACE:'
    cov = sig.rcov()
    random_trace = f.random_trace(covering = cov, debug = True)
    print cov
    print random_trace
    print f.test_string(random_trace)
    

"""
Invocation
"""
if __name__ == '__main__':
    main()
